<?php

class TrieTree {

    private $tree;

    public function __construct($strList) {

        $this->tree = $this->buildTrieTree($strList);

    }

    public function queryPrefix($prefix) {

        $charArray = preg_split('/(?<!^)(?!$)/u', $prefix);

        $subTree = $this->findSubTree($charArray, $this->tree);



        $words = $this->traverseTree($subTree);



        foreach($words as &$word) {

            $word = $prefix . $word;

        }

        return $words;

    }

    public function findSubTree($charArray, $tree) {

        foreach($charArray as $char) {

            if (in_array($char, array_keys($tree))) {

                $tree = $tree[$char];

            } else {

                return [];

            }

        }

        return $tree;

    }

    public function traverseTree($tree) {

        $words = [];

        foreach ($tree as $node => $subTree) {

            if (empty($subTree)) {

                $words[] = $node;

                return $words;

            }



            $chars = $this->traverseTree($subTree);

            foreach($chars as $char) {

                $words[] = $node . $char;

            }

        }

        return $words;

    }

    /**

     * 将字符串的数组构建成Trie树

     *

     * @param [array] $strList

     * @return void

     */

    public function buildTrieTree($strList) {

        $tree = [];

        foreach($strList as $str) {

            $charArray = preg_split('/(?<!^)(?!$)/u', $str); 

            $tree = $this->addWordToTrieTree($charArray, $tree);

        }

        return $tree;

    }

    /**

     * 把一个词加入到Trie树中

     *

     * @param [type] $charArray

     * @param [type] $tree

     * @return void

     */

    public function addWordToTrieTree($charArray, $tree) {

        if (count($charArray) == 0) {

            return [];

        }

        $char = $charArray[0];



        $leftStr = array_slice($charArray, 1);

        $tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);



        return $tree;

    }

    public function getTree() {

        return $this->tree;

    }

}

$strList = ['春风十里','春天在哪里','一百万个可能','一千年以后','后来','后来的我们','春天里','后会无期'];

$trieTree = new TrieTree($strList);

print_r($trieTree->getTree());

$prefix = '春';

$queryRes = $trieTree->queryPrefix($prefix);

print_r($queryRes);